#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
typedef struct linkedlist
{
	int i;
	struct linkedlist *next;
}llist;

int push(llist **head,int i)
{
	llist *temp=(*head);
	if((*head)==NULL)
	{
		(*head)=(llist *)malloc(sizeof(llist));
		(*head)->i=i;
		(*head)->next=NULL;
		return 0;
	}
	while(temp->next!=NULL)
	{
		temp=temp->next;
	}
	temp->next=(llist *)malloc(sizeof(llist));
	temp->next->i=i;
	temp->next->next=NULL;
	return 0;
}

int printlist(llist *head)
{
	llist *tmp=head;
	while(tmp!=NULL)
	{
		printf("%d ",tmp->i);
		tmp=tmp->next;
	}
	printf("\n");
}

int freelist(llist *head)
{
	llist *tmp=head;
	while(tmp!=NULL)
	{
		tmp=tmp->next;
		free(head);
		head=tmp;
	}
}

llist *mergellist(llist *head,llist *head2)
{
	llist *headref;
	int i,j,k;
	if(head==NULL)
	{
		return head2;
	}
	else if(head2==NULL)
	{
		return head;
	}
	if(head->i<head2->i)
	{
		headref=head;
		headref->next=mergellist(head->next,head2);
	}
	else
	{
		headref=head2;
		headref->next=mergellist(head,head2->next);
	}
	return headref;
}
	
int mergesortlist(llist **head)
{
	llist *head2;
	llist *slow,*fast;
	slow=(*head);
	fast=(*head);
	if((*head)==NULL||(*head)->next==NULL) return;
	while(fast->next!=NULL)
	{
		fast=fast->next;
		if(fast->next!=NULL) slow=slow->next,fast=fast->next;
	}
	head2=slow->next;
	slow->next=NULL;
	mergesortlist(head);
	mergesortlist(&head2);
	(*head)=mergellist((*head),head2);
	return 0;
}

int main()
{
	int i,j,k;
	int n,temp;
	llist *tmp;
	llist *head=NULL;
	scanf("%d",&n);
	for(i=0;i<n;i++) 
	{
		scanf("%d",&temp);
		push(&head,temp);
	}
	printlist(head);
	mergesortlist(&head);
	printlist(head);
	freelist(head);
	return 0;
}


